{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Insert Into Bits LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: insertBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #插入"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整型数字 <code>N</code> 与 <code>M</code>，以及表示比特位置的 <code>i</code> 与 <code>j</code>（<code>i <= j</code>，且从 0 位开始计算）。</p>\n",
    "\n",
    "<p>编写一种方法，使 <code>M</code> 对应的二进制数字插入 <code>N</code> 对应的二进制数字的第 <code>i ~ j</code> 位区域，不足之处用 <code>0</code> 补齐。具体插入过程如图所示。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1610104070-NuLVQi-05.01.gif\" style=\"width: 267px; height: 200px;\" /></p>\n",
    "\n",
    "<p>题目保证从 <code>i</code> 位到 <code>j</code> 位足以容纳 <code>M</code>， 例如： <code>M = 10011</code>，则 <code>i～j</code> 区域至少可容纳 5 位。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：N = 1024(10000000000), M = 19(10011), i = 2, j = 6\n",
    "<strong> 输出</strong>：N = 1100(10001001100)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>： N = 0, M = 31(11111), i = 0, j = 4\n",
    "<strong> 输出</strong>：N = 31(11111)\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [insert-into-bits-lcci](https://leetcode.cn/problems/insert-into-bits-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [insert-into-bits-lcci](https://leetcode.cn/problems/insert-into-bits-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        if N < M:\n",
    "            return M\n",
    "        tem = '1'*(32-j-1) + '0'*(j-i+1) + '1'*i\n",
    "        return (int(tem, 2) & N | (M<<i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        mask = (((1<<64)-1) << (j+1)) | (1 << i)-1\n",
    "        # print(bin(mask))\n",
    "        return N & mask | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "\n",
    "        for k in range(i, j+1):\n",
    "            N &= ~(1 << k)\n",
    "        return N | (M<<i)\n",
    "\n",
    "\n",
    "# 将N 的[i, j]位都置零 再将M和N的i位开始与\n",
    "# 作者：stepstep\n",
    "# 链接：https://leetcode.cn/problems/insert-into-bits-lcci/solutions/276054/wei-yun-suan-by-stepstep/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        t = i\n",
    "        while t > 0:\n",
    "            M <<= 1\n",
    "            t -= 1\n",
    "        print(bin(N))\n",
    "        print(bin(M))\n",
    "        for k in range(i, j + 1):\n",
    "            if (1 << k) & M:\n",
    "                N |= (1 << k)\n",
    "            else:\n",
    "                N &= ~(1 << k)\n",
    "        print(bin(N))\n",
    "        return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        item=1\n",
    "        num=0\n",
    "        for k1 in range(j-i+1):\n",
    "            num+=item\n",
    "            item*=2\n",
    "\n",
    "        num=num<<i\n",
    "        N=N & ~num\n",
    "\n",
    "        for k2 in range(i):\n",
    "            M*=2\n",
    "\n",
    "        N=M ^ N\n",
    "        return N\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        return (((-(((1<<(j-i+1))-1)<<i))-1)&N)|(M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        nb = self.numToBit(N)\n",
    "        mb = self.numToBit(M)\n",
    "        while len(nb) < j + 1:\n",
    "            nb = \"0\" + nb\n",
    "        while len(mb) < j - i + 1:\n",
    "            mb = \"0\" + mb\n",
    "        n = len(nb)\n",
    "        m = len(mb)\n",
    "        new_nb = nb[:n-i-m] + mb + nb[n - i:n]\n",
    "        return int(new_nb, 2)\n",
    "\n",
    "    def numToBit(self, num):\n",
    "        if num >= 0:\n",
    "            return bin(num)[2:]\n",
    "        else:\n",
    "            return bin(num & 0xffffffff)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i, j+1):\n",
    "            N &= ~(1<<k)\n",
    "        return N | (M << i)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~((((1 << (j + 1)) - 1) >> i) << i)\n",
    "        return N | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        res = 0\n",
    "        count = 0\n",
    "        while N or M:\n",
    "            if i <= count <= j:\n",
    "                res += M%2 * (2 ** count)\n",
    "                M >>= 1\n",
    "            elif count < i:\n",
    "                res += N%2 * (2 ** count)\n",
    "            else:\n",
    "                res += N%2 * (2 ** count)\n",
    "                M >>= 1\n",
    "            N >>= 1\n",
    "            count += 1\n",
    "        return res\n",
    "        \n",
    "        # #   将 n 的 i - j 位变为 0\n",
    "        # for k in range(i, j + 1):\n",
    "        #     N &= ~(1 << k)\n",
    "        # #   将 m 左移 i 位 ,与 n 做或运算,等价于将 m 插入 i - j 位\n",
    "        # print(bin(N), bin(M))\n",
    "        # return N | (M << i)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        if N<=M: \n",
    "            return M\n",
    "        tem = \"1\"*(31-j) + \"0\"*(j-i+1) + \"1\"*i\n",
    "        return (int(tem, base=2) & N) | (M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        s = list(bin(N)[2:])\n",
    "        ss = list(bin(M)[2:])\n",
    "        ss.reverse()\n",
    "        s.reverse()\n",
    "        \n",
    "        if len(s) < j+1:\n",
    "            s += ['0'] * (j+1-len(s))\n",
    "        if len(ss) < j-i+1:\n",
    "            ss += ['0'] * (j-i+1-len(ss))\n",
    "        # print(s, ss)\n",
    "\n",
    "        for k in range(i,j+1):\n",
    "            s[k] = ss[k-i]\n",
    "        \n",
    "        s.reverse()\n",
    "        return int(''.join(s), 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        return (((-(((1<<(j-i+1))-1)<<i))-1)&N)|(M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef insertBits(self, n, m, i, j):\n",
    "\t\tmark = 0\n",
    "\t\tfor k in range(i, j + 1):\n",
    "\t\t\tmark |= 1 << k\n",
    "\t\treturn n ^ (n & mark) | m << i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        mask = (((1<<64)-1) << (j+1)) | (1 << i)-1\n",
    "        # print(bin(mask))\n",
    "        return N & mask | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N&=~((((1<<(j+1))-1)>>i)<<i)\n",
    "        return N|(M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for r in range(i,j+1):\n",
    "            N&=~(1<<r)\n",
    "        N=N|(M<<i)\n",
    "        return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        n = '0'*(j-i+1)+str(bin(N))[2:]\n",
    "        m = str(bin(M))[2:]\n",
    "        if len(m)<j-i+1:\n",
    "            m = '0'*(j-i+1-len(m))+m\n",
    "        nLen = len(n)\n",
    "        k = n[:nLen-j-1]+m+n[nLen-i:]\n",
    "        return int(k,2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        mask = (1<<(j+1))-1-(1<<i) + 1\n",
    "        N = N & (~mask)\n",
    "        N = N | (M<<i)\n",
    "        return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        # 将n的i-j位变为0\n",
    "        for k in range(i, j + 1):\n",
    "            N &= ~(1<<k)\n",
    "        # 将m左移i位，与n做或运算\n",
    "        return N | (M <<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        res = 0\n",
    "        count = 0\n",
    "        while N or M:\n",
    "            if i <= count <= j:\n",
    "                res += M%2 * (2 ** count)\n",
    "                M >>= 1\n",
    "            else:\n",
    "                res += N%2 * (2 ** count)\n",
    "            N >>= 1\n",
    "            count += 1\n",
    "        return res\n",
    "        \n",
    "        # #   将 n 的 i - j 位变为 0\n",
    "        # for k in range(i, j + 1):\n",
    "        #     N &= ~(1 << k)\n",
    "        # #   将 m 左移 i 位 ,与 n 做或运算,等价于将 m 插入 i - j 位\n",
    "        # print(bin(N), bin(M))\n",
    "        # return N | (M << i)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        if N<=M:\n",
    "            return M\n",
    "        tem = \"1\"*(32-j-1) + \"0\"*(j-i+1) + \"1\"*i\n",
    "        return (int(tem,base=2)&N)|(M<<i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i, j + 1):\n",
    "            N = N & ~(1 << k)\n",
    "        \n",
    "        return N | M << i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        str_M = bin(M)[2:]#0b前缀要舍弃\n",
    "        str_N = bin(N)[2:]\n",
    "        length = j - i + 1\n",
    "        length_M = len(str_M)\n",
    "        length_N = len(str_N)\n",
    "        \n",
    "        if length_M == length:\n",
    "            insert_str = str_M\n",
    "            res = str_N[:-(j+1)] + insert_str +str_N[length_N-i:]\n",
    "            return int(res,2)\n",
    "        else:\n",
    "            insert_str = '0' * (j-i+1-length_M) + str_M\n",
    "            res = str_N[:-(j+1)] + insert_str + str_N[length_N-i:]\n",
    "            return int(res,2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        H = ~((((1<<(j + 1))-1)>>i)<<i)\n",
    "        N = H & N\n",
    "        return N | (M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        mask = (((1<<32)-1) << (j+1)) | (1 << i)-1\n",
    "        # print(bin(mask))\n",
    "        return N & mask | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        t = 2 ** (j - i + 1) - 1\n",
    "        t <<= i  \n",
    "        t = ~t  \n",
    "        M <<= i  \n",
    "        return N & t | M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "\t\treturn N & ~((((1 << (j + 1)) - 1) >> i) << i) | (M << i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(j-i+1):\n",
    "            N ^= ((M & 1<<k) << i) ^ (N & 1<<(k+i))\n",
    "        return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        mask = (((1<<32)-1) << (j+1)) | (1 << i)-1\n",
    "        # print(bin(mask))\n",
    "        return N & mask | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "\n",
    "        def getbinary(temp):\n",
    "            binary = []\n",
    "            while temp > 0:\n",
    "                binary.append(temp % 2)\n",
    "                temp = temp // 2\n",
    "            return binary\n",
    "        binaryN = getbinary(N)\n",
    "        binaryM = getbinary(M)\n",
    "\n",
    "        for pos in range(i, j+1):\n",
    "            if pos < len(binaryN):\n",
    "                binaryN[pos] = binaryM[pos-i] if pos-i < len(binaryM) else 0\n",
    "            else:\n",
    "                binaryN.append(binaryM[pos-i]) if pos-i < len(binaryM) else 0\n",
    "\n",
    "\n",
    "        return sum([2**i * v for i, v in enumerate(binaryN)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        if N<M: return M\n",
    "        tem=\"1\"*(32-j-1)+\"0\"*(j-i+1)+\"1\"*i\n",
    "        return (int(tem,base=2)&N)|(M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        M = M << i\n",
    "        sub = 0\n",
    "        for p in range(i, j+1):\n",
    "            sub += N&(1<<p)\n",
    "        return N-sub+M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~((((1 << (j + 1)) - 1) >> i) << i)\n",
    "        return N | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        m = len(bin(M))\n",
    "        tmp=list(bin(N)[2:])[::-1]\n",
    "        m_lst = list(bin(M)[2:][::-1])\n",
    "        tmp[i:j+1] = m_lst if m >= j-i+3 else m_lst+[\"0\" for _ in range(j-i+3-m)]\n",
    "        return int(\"\".join(tmp[::-1]),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~((((1 << (j+1)) -1) >> i) << i)\n",
    "        return N | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~((((1 << (j+1)) -1) >> i) << i)\n",
    "        return N | (M << i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(j-i+1):\n",
    "            N ^= ((M & 1<<k) << i) ^ (N & 1<<(k+i))\n",
    "        return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i, j + 1):\n",
    "            N = N & ~(1 << k)\n",
    "        \n",
    "        return N | M << i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        if N<=M: return M\n",
    "        tem = \"1\"*(32-j-1) + \"0\"*(j-i+1) + \"1\"*i\n",
    "        return (int(tem, base=2)&N) | (M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        m = bin(M)[2:]\n",
    "        n = bin(N)[2:][::-1]\n",
    "        res = n[:i] + m.zfill(j-i+1)[::-1] + n[j+1:]\n",
    "        return int(res[::-1],2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        #巧妙位运算\n",
    "        for x in range(i,j+1):\n",
    "            if M&(1<<(x-i)): N|=(1<<x)\n",
    "            else: N&=~(1<<x)    \n",
    "        return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~((((1 << (j + 1)) - 1) >> i) << i)\n",
    "        return N | (M << i)\n",
    "\n",
    "        # 1 << (j + 1) gives:\n",
    "        # 1000000 (1 and j+1 of 0)\n",
    "\n",
    "        # 1 << (j + 1) - 1 gives:\n",
    "        # 111111 (j+1 of 1)\n",
    "\n",
    "        # foo >> i gives:\n",
    "        # 111 (right side i of 1 is removed)\n",
    "\n",
    "        # foo << i gives:\n",
    "        # 111000 (right side insert i of 0)\n",
    "\n",
    "        # now we have all location that need to be set to 0 with 1 now\n",
    "\n",
    "        # ~foo gives:\n",
    "        # ...111000111 (used for and operation)\n",
    "\n",
    "        # with current foo:\n",
    "        # all digits after & with 1 will not changed\n",
    "        # all digits after & with 0 will set to 0\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        num = i-1\n",
    "        for _ in range(j-i+1):\n",
    "            num += 1\n",
    "            N = N & (~(1<<num))\n",
    "        return N | M << i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        pos = i\n",
    "        while pos <= j:\n",
    "            N ^= N & (2 ** pos)\n",
    "            pos += 1\n",
    "        N |= M << i\n",
    "        \n",
    "        return N "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i, j+1):\n",
    "            if N & (1 << k):\n",
    "                N -= 1 << k\n",
    "        return N | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i, j+1):\n",
    "            N &= ~(1<<k)\n",
    "        \n",
    "        return N | (M << i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for index in range(i, j+1):\n",
    "            N &= ~(1 << index)\n",
    "        return N + (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for x in range(i, j+1):\n",
    "           N &= ~(1<<x)\n",
    "        N += (M << i)\n",
    "        return N\n",
    "\n",
    "     \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        if N<=M: return M\n",
    "        # 构建32位字符串下标i-j为0，其他为1\n",
    "        tem = \"1\"*(32-j-1) + \"0\"*(j-i+1) + \"1\"*i\n",
    "        # 将N的i-j为置0\n",
    "        # 将M左移i位\n",
    "        # 两者相或即可\n",
    "        return (int(tem,base=2)&N)|(M<<i)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        one = ~0\n",
    "        left = one <<(j + 1)\n",
    "        right = (1<<i) - 1\n",
    "        mask = left | right\n",
    "\n",
    "        n = mask & N\n",
    "\n",
    "        m = M << i\n",
    "        return n | m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i,j+1):\n",
    "            N &= ~(1<<k)\n",
    "        return N | (M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        # res = 0\n",
    "        # count = 0\n",
    "        # while N or M:\n",
    "        #     if i <= count <= j:\n",
    "        #         res += M%2 * (2 ** count)\n",
    "        #         M >>= 1\n",
    "        #     else:\n",
    "        #         res += N%2 * (2 ** count)\n",
    "        #     N >>= 1\n",
    "        #     count += 1\n",
    "        # return res\n",
    "        \n",
    "        #   将 n 的 i - j 位变为 0\n",
    "        for k in range(i, j + 1):\n",
    "            N &= ~(1 << k)\n",
    "        #   将 m 左移 i 位 ,与 n 做或运算,等价于将 m 插入 i - j 位\n",
    "        return N | (M << i)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "#         N1=(N>>(j+1))<<(j+1)\n",
    "#         N2=((1<<i)-1)&N\n",
    "#         # N3=N1|N2\n",
    "#         return (N1|N2)|(M<<i)\n",
    "        \n",
    "\n",
    "### 网：使用取反\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~((((1 << (j+1)) -1) >> i) << i)\n",
    "        return N | (M << i)\n",
    "\n",
    "# 作者：雨点\n",
    "# 链接：https://leetcode.cn/problems/insert-into-bits-lcci/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        str_bin = str(bin(N))[2:]\n",
    "        N_list = []\n",
    "        for k in range(32-len(str_bin)):\n",
    "            N_list.append('0')\n",
    "        for k in str_bin:\n",
    "            N_list.append(k)\n",
    "        N_list = N_list[::-1]\n",
    "        len_s = j - i + 1\n",
    "        str_bin = str(bin(M))[2:]\n",
    "        M_list = []\n",
    "        for k in range(len_s-len(str_bin)):\n",
    "            M_list.append('0')\n",
    "        for k in str_bin:\n",
    "            M_list.append(k)\n",
    "        M_list = M_list[::-1]\n",
    "        index = 0\n",
    "        for k in range(i,j+1):\n",
    "            N_list[k] = M_list[index]\n",
    "            index = index + 1\n",
    "        print(N_list)\n",
    "        s = ''.join(N_list[::-1])\n",
    "        print(s)\n",
    "        return int(s,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~((((1 << (j+1)) -1) >> i) << i)\n",
    "        return N | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i, j+1):\n",
    "            if N & (1 << k):\n",
    "                N -= (1 << k)\n",
    "        # print(N)\n",
    "        return N + (M << i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "       \n",
    "       for k in range(i,j+1):\n",
    "           N &= ~(1<<k)\n",
    "       return N|(M << i)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N &= ~(((1 << (j - i + 1)) - 1) << i)\n",
    "        return N | (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        for k in range(i, j + 1):\n",
    "            N &= ~(1 << k)\n",
    "        print(N)\n",
    "        return N + (M << i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        N1=(N>>(j+1))<<(j+1)\n",
    "        N2=((1<<i)-1)&N\n",
    "        # N3=N1|N2\n",
    "        return (N1|N2)|(M<<i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        as_str = bin(N)[2:].lstrip('0')\n",
    "        to_insert = bin(M)[2:].rjust(j - i + 1, '0')\n",
    "        new_str = as_str[0:-j - 1] + to_insert\n",
    "        if i > 0:\n",
    "            new_str += as_str[-i:len(as_str)]\n",
    "        return int(new_str, 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        return ((~(((1<<(j-i+1))-1)<<i))&N)|(M<<i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insertBits(self, N: int, M: int, i: int, j: int) -> int:\n",
    "        bn, bm = bin(N)[2:][::-1], bin(M)[2:][::-1]\n",
    "        bn = bn[:i] + '0'*(j-i+1) + bn[j+1:]\n",
    "        bn = bn[:i] + bm + bn[i+len(bm):]\n",
    "        return int('0b' + bn[::-1], 2)\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
